/**
 * Project of Vehicle Routing Problem with Time Windows implements 
 * some of well-known algorithms for solving VRPTW and presents new 
 * one.
 *
 * @author Michal Drobny  
 */

package heuristic;

import java.util.List;
import java.util.Vector;

import logic.algorithm.Algorithm;
import logic.algorithm.AlgorithmResult;
import logic.algorithm.AlgorithmState;
import logic.car.VehicleProvider;
import logic.destination.Destination;
import logic.evaluator.Evaluator;
import logic.restriction.enumeration.ChangeCycleVariant;
import logic.restriction.enumeration.IterationType;
import logic.restrictionAdapter.RestrictionAdapter;
import logic.route.Cycle;
import logic.route.Route;

/**
 * Represents the Nearest Neighbor method for solving VRP problem.
 * 
 * @author Michal Drobny
 * @date 19.10.2014
 */
public class NearestNeighbor implements Algorithm {

	@Override
	public AlgorithmResult compute(Route route, Destination start,
			Evaluator evaluator, RestrictionAdapter restrictionAdapter, VehicleProvider vehicleProvider) {

		if (route == null || start == null || evaluator == null
				|| restrictionAdapter == null || vehicleProvider == null)
			return new AlgorithmResult(AlgorithmState.BAD_PARAMETERS, null,
					route);

		if (!route.getDestinations().contains(start))
			return new AlgorithmResult(AlgorithmState.BAD_START_DESTINATION,
					null, route);

		List<Cycle> cycles = new Vector<Cycle>();
		List<Destination> unusedDestinations = new Vector<Destination>(
				route.getDestinations());

		unusedDestinations.remove(start);
		Cycle cycle = new Cycle();
		cycle.addToEnd(start);

		Destination from = start;
		while (!unusedDestinations.isEmpty()) {
			Double bestValue = Double.MAX_VALUE;
			Destination bestDestination = null, previousDestination = null;

			for (Destination destination : unusedDestinations) {
				if (!restrictionAdapter.canIterate(IterationType.DESTINATION_ONLY, from, destination))
					continue;

				Double currentValue = evaluator.evaluate(from, destination);
				if (currentValue != -1 && currentValue < bestValue) {
					bestValue = currentValue;
					previousDestination = from;
					bestDestination = destination;
				} else
					continue;
			}

			if (bestDestination != null && restrictionAdapter.canIterate(IterationType.DESTINATION_ONLY, previousDestination, bestDestination)) {
				cycle.addToEnd(bestDestination);
				unusedDestinations.remove(bestDestination);
				from = bestDestination;
				restrictionAdapter.iterate(IterationType.DESTINATION_ONLY, previousDestination, bestDestination);
			} else {
				if (cycle.size() == 1 || !restrictionAdapter.canNewCycle(ChangeCycleVariant.VEHICLE_PROVIDER, vehicleProvider))
					return new AlgorithmResult(AlgorithmState.NO_SOLUTION,
							null, route);
				else {
					cycles.add(cycle);
					restrictionAdapter.newCycle(ChangeCycleVariant.VEHICLE_PROVIDER, vehicleProvider);;
					cycle = new Cycle();
					cycle.addToEnd(start);
					from = start;
				}
			}
		}
		
		cycles.add(cycle);
		AlgorithmState resultState;
		if (cycles.size() == 1)
			resultState = AlgorithmState.ONE_CYCLE_SOLUTION;
		else
			resultState = AlgorithmState.MORE_CYCLE_SOLUTION;
		
		return new AlgorithmResult(resultState,
				cycles.toArray(new Cycle[cycles.size()]), route);
	}
}